package com.xiaoyu.string;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: 递归算法!,后面的生成依赖于前面
 *
 *  22.括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 * @author: YuWenYi
 * @create: 2021-04-25 15:07
 **/


public class GenerateParenthesis_22 {
    List<String> result = new ArrayList<>();
    public  List<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
       /* getParenthesis("",n,n);
        return result;*/
        dfs("", n,n ,result);
        return result;
    }

    private void getParenthesis(String s, int left, int right) {
        if (left == 0 && right==0){
            result.add(s);
            return;
        }
        //如果右边括号的数量等于左边括号的数量,那么下一个只能是左括号!
        if (left == right){
            getParenthesis(s+"(",left-1,right);
        }else if (left < right){
            //如果剩余右括号数量大于左括号数量,即实际左括号数量大于右括号数量的时候!
           if (left > 0){
               getParenthesis(s+"(",left-1,right);
           }
           getParenthesis(s+")",left,right-1);
        }
    }


    /*
    * 这其实就是一颗隐式的二叉树,因此我们可以使用DFS去对它进行操作!
    *   当前左右括号都有大于 0 个可以使用的时候，才产生分支；
        产生左分支的时候，只看当前是否还有左括号可以使用；
        产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
        在左边和右边剩余的括号数都等于 0 的时候结算。


        由于字符串特性,每次都是使用一个新的字符串去进行递归,如果不满足条件就丢弃了那个字符串,
        原来的字符串不受到影响,即回到了先前的状态,因此这隐式的使用了回溯算法
    * */
    public void dfs(String s,int left,int right,List<String> result){
        if (left == 0 && right == 0){
            result.add(s);
            return;
        }
        //如果左大于右,就剪枝,丢弃
        if (left > right) return;

        if (left > 0){
            dfs(s+"(", left-1, right, result);
        }

        if (right > 0){
            dfs(s+")", left, right-1, result);
        }
    }


    public static void main(String[] args) {
        GenerateParenthesis_22 parenthesis = new GenerateParenthesis_22();
        int n = 3;
        List<String> list = parenthesis.generateParenthesis(n);
        System.out.println(list);
    }

}
